class Solution {
public:
  /*
  // 暴力循环
    int maxsum(vector<int>& v){
        int res = INT_MIN;
        for(int i : v)
            res = res>i ? res : i;
        return res;
    }
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        size_t size = nums.size();
        for(int i = 0; i <= size-k; ++i){
            int sum = 0;
            vector<int> temp;
            for(int j = i; j < i+k; ++j){
                sum += nums[j];
                temp.push_back(nums[j]);
            }
            res.push_back(maxsum(temp));
        }
        return res;
    }
  */
  
    class MyQueue{
    public:
        deque<int> dq;   // 搞个单调的双端对列
        /* 如果val大于队尾元素数值，那么从队尾出队直到val <= 队头元素数值为止。
        这样就保持了队列里的数值是单调从大到小的了。*/
        void push(int val){
            while(!dq.empty() && val > dq.back())
                dq.pop_back();
            dq.push_back(val);
        }
        // 如果窗口移除的元素val等于单调队列的出口元素，那么弹出队头元素，否则不用操作
        void pop(int val){
            if(!dq.empty() && val == dq.front())
                dq.pop_front();
        }

        int getMax(){
            return dq.front();
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        size_t size = nums.size();
        if(size == 0) return res;
        MyQueue mq;  

        for(int i = 0; i < k; ++i)
            mq.push(nums[i]);
        res.push_back(mq.getMax());  // 记录第一个窗口最值
        // 开始滑动
        for(int i = k; i < size; ++i){
            mq.pop(nums[i-k]);
            mq.push(nums[i]);
            res.push_back(mq.getMax());
        }
        
        return res;
    }

};